/**
 * @ClassName Code03_DoubleEndsQueueToStackAndQueue
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/12/13 12:23
 */

import com.sun.org.apache.bcel.internal.generic.NEW;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 双端队列实现栈和队列
 * 底层是双链表
 */
public class Code03_DoubleEndsQueueToStackAndQueue {
    // 双链表结点
    public static class Node<T> {
        public T value;
        public Node<T> last;
        public Node<T> next;

        public Node(T value) {
            this.value = value;
        }
    }

    // 双端队列
    public static class DoubleEndsQueue<T> {
        // 头结点
        public Node<T> head;
        // 尾结点
        public Node<T> tail;

        // 头插法
        public void addHead(T value) {
            Node<T> cur = new Node<>(value);
            if (isEmpty()) {
                head = cur;
                tail = cur;
            } else {
                cur.next = head;
                head.last = cur;
                head = cur;
            }
        }

        // 尾插法
        public void addBottom(T value) {
            Node<T> cur = new Node<>(value);
            if (isEmpty()) {
                head = cur;
                tail = cur;
            } else {
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
        }

        // 头删法
        public T popHead() {
            if (isEmpty()) {
                return null;
            }
            Node<T> cur = head;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                cur.next = null;
                head.last = null;
            }
            return cur.value;
        }

        // 尾删法
        public T popBottom() {
            if (isEmpty()) {
                return null;
            }
            Node<T> cur = tail;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
                cur.last = null;
            }
            return cur.value;
        }

        public boolean isEmpty() {
            return head == null;
        }
    }

    public static class MyStack<T> {
        private DoubleEndsQueue<T> queue;

        public MyStack() {
            queue = new DoubleEndsQueue<T>();
        }

        // 头插法的入栈
        public void push(T value) {
            queue.addHead(value);
        }

        // 头插法的出栈
        public T pop() {
            return queue.popHead();
        }

        // 判空
        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }

    public static class MyQueue<T> {
        private DoubleEndsQueue<T> queue;

        public MyQueue() {
            queue = new DoubleEndsQueue<T>();
        }

        // 队列进队尾插法
        public void offer(T value) {
            queue.addBottom(value);
        }

        // 队列出队头删法
        public T poll () {
            return queue.popHead();
        }

        // 判空
        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }

    // 检测弹出的数是否相同
    public static boolean isEqual(Integer o1,Integer o2) {
        if (o1 == null && o2 != null || o1 != null && o2 == null) {
            return false;
        }
        if (o1 == null && o2 == null) {
            return true;
        }
        return o1.equals(o2);
    }

    public static void main(String[] args) {
        int testDataNums = 100;
        int value = 1000;
        int testTimes = 100000;
        System.out.println("开始测试");
        for (int i = 0; i < testTimes; i++) {
            MyStack<Integer> myStack = new MyStack<>();
            Stack<Integer> stack = new Stack<>();
            MyQueue<Integer> myQueue = new MyQueue<>();
            Queue<Integer> queue = new LinkedList<>();
            boolean flagStack = true;
            boolean flagQueue = true;
            for (int j = 0; j < testDataNums; j++) {
                int numStack = (int) (Math.random() * (value + 1));
                if (stack.isEmpty()) {
                    myStack.push(numStack);
                    stack.push(numStack);
                } else {
                    if (Math.random() < 0.5) {
                        myStack.push(numStack);
                        stack.push(numStack);
                    } else {
                        if (!isEqual(myStack.pop(),stack.pop())) {
                            System.out.println("stack error!!!");
                            flagStack = false;
                        }
                    }
                }
                int numQueue = (int) (Math.random() * (value +1));
                if (queue.isEmpty()) {
                    myQueue.offer(numQueue);
                    queue.offer(numQueue);
                } else {
                    if (Math.random() < 0.5) {
                        myQueue.offer(numQueue);
                        queue.offer(numQueue);
                    } else {
                        if (!isEqual(myQueue.poll(),queue.poll())) {
                            System.out.println("queue error!!!");
                            flagQueue = false;
                        }
                    }
                }
                if (!flagStack || !flagQueue) {
                    System.out.println("测试异常");
                    break;
                }
            }

        }
        System.out.println("结束测试");
    }
}
